package dynamicprogramming;

import org.junit.Test;

/**
 * @author DuJiabao
 * @create 2021-01-01 15:54
 * 极客时间 40节
 */
public class DynamicProgrammingMethod2 extends Example1 {
    @Override
    public void f(int[] weight, int n, int w) {
        // 一行列表即可
        boolean[] state = new boolean[w + 1];
        state[0] = true;  // 什么都不放 第一个物品之前的状态
        //第一个物品及以后的状态
        for (int i = 0; i < n; i++) {  //遍历所有物品
            for (int j = w - weight[i]; j >= 0; j--) { // 从能放物品位置的开始，倒序。很巧妙，解决了前面设true，影响后面，重复摆放的情况。
                if (state[j]) {
                    state[j + weight[i]] = true;  // 放！肯定能放的，因为之前已经判断过了。
                }
            }
        }
        // 遍历查找
        for (int i = w; i >= 0; i--) {
            if (state[i]) {
                maxW = i;
                return;
            }
        }
    }

    @Test
    public void test() {
//        f(weight, n, w);
        f(new int[]{0, 1, 1, 2, 1}, n, w);
        System.out.println(maxW);
    }

}
